package leetcode_1501_1600;

public class LeeCode_1537_wrong {
    public static void main(String[] args) {
        System.out.println(maxSum(new int[]{2, 4, 5, 8, 10}, new int[]{4, 6, 8, 9}));
        System.out.println(maxSum(new int[]{1,2,3}, new int[]{4,5,6}));
    }

    private static int maxSum(int[] nums1, int[] nums2) {
        long mod = (long) (1e9 + 7);
        int m = nums1.length, n = nums2.length;
        long[] dp1 = new long[m];
        long[] dp2 = new long[n];
        dfs(dp1, dp2, nums1, nums2, 1, 0, 0);
        dfs(dp1, dp2, nums1, nums2, 2, 0, 0);
        return (int) (Math.max(dp1[0], dp2[0]) % mod);
    }

    private static long dfs(long[] dp1, long[] dp2, int[] nums1, int[] nums2, int which, int i1, int i2) {
        int m = nums1.length, n = nums2.length;
        if (which == 1) {
            if (i1 >= m)
                return 0;
            if (dp1[i1] > 0)
                return dp1[i1];
            while (i2 < n && nums2[i2] < nums1[i1]) {
                i2++;
            }
            if (i2 < n && nums2[i2] == nums1[i1]) {
                dp1[i1] = Math.max(dfs(dp1, dp2, nums1, nums2, 1, i1 + 1, i2),
                        dfs(dp1, dp2, nums1, nums2, 2, i1 + 1, i2 + 1)) + nums1[i1];
            } else {
                dp1[i1] = dfs(dp1, dp2, nums1, nums2, 1, i1 + 1, i2) + nums1[i1];
            }
            return dp1[i1];
        } else {
            if (i2 >= n)
                return 0;
            if (dp2[i2] > 0)
                return dp2[i2];
            while (i1 < m && nums1[i1] < nums2[i2]) {
                i1++;
            }
            if (i1 < m && nums1[i1] == nums2[i2]) {
                dp2[i2] = Math.max(dfs(dp1, dp2, nums1, nums2, 2, i2 + 1, i1),
                        dfs(dp1, dp2, nums1, nums2, 1, i1 + 1, i2 + 1)) + nums2[i2];
            }else {
                dp2[i2] = dfs(dp1, dp2, nums1, nums2, 2, i1, i2 + 1) + nums2[i2];
            }
            return dp2[i2];
        }
    }
}